      1  import java.util.ArrayList;

      2

      3  /**

      4     The sort method of this class sorts an array, using the Shell

      5     sort algorithm.

      6  */

      7  public class ShellSorter

      8  {

      9     /**

     10        Sorts an array, using selection sort.

     11        @param a the array to sort

     12     */

     13     public static void sort(int[] a)

     14     {

     15        // Generate the sequence values

     16        ArrayList<Integer> columns = new ArrayList<Integer>();

     17        int c = 1;

     18        while (c < a.length)

     19        {

     20           columns.add(c);

     21           c = 3 * c + 1;

     22        }

     23

     24        // For each column count, sort all columns

     25        for (int s = columns.size() - 1; s >= 0; s--)

     26        {

     27           c = columns.get(s);

     28           for (int k = 0; k < c; k++)

     29           {

     30              insertionSort(a, k, c);

     31           }

     32        }

     33     }

     34

     35     /**

     36        Sorts a column, using insertion sort.

     37        @param a the array to sort

     38        @param k the index of the first element in the column

     39        @param c the gap between elements in the column

     40     */

     41     public static void insertionSort(int[] a, int k, int c)

     42     {

     43        for (int i = k + c; i < a.length; i = i + c)

     44        {

     45           int next = a[i];

     46           // Move all larger elements up

     47           int j = i;

     48           while (j >= c && a[j - c] > next)

     49           {

     50              a[j] = a[j - c];

     51              j = j - c;

     52           }

     53           // Insert the element

     54           a[j] = next;

     55        }

     56     }

     57  }